package th.retrofit.lib;

/**
 * https://leetcode-cn.com/problems/wildcard-matching/
 * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符串（包括空字符串）。
 * 两个字符串完全匹配才算匹配成功。
 * 说明:
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *
 */

public class Solution44 {

    public boolean isMatch(String s, String p) {
        int sLen = s.length();
        int pLen = p.length();
        boolean[][] dp = new boolean[sLen + 1][pLen + 1];
        dp[0][0] = true;
        for (int i = 0; i <= sLen; i++) {
            for (int j = 1; j <= pLen; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1];
                    if (i > 0) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                } else if (i > 0 && isCharacterMatch(s.charAt(i - 1), p.charAt(j - 1))) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[sLen][pLen];
    }

    private boolean isCharacterMatch(char target, char source) {
        return source =='?' || target == source;
    }

    public static void main(String[] args) {
        System.out.println(new Solution44().isMatch("aa", "a"));
    }
}
